package com.dubious.interview.euler;

import java.util.List;

import org.joda.time.DateTime;

public class Problem12 {

    public static void main(String[] args) {
        //@formatter:off
        // if we break down a number n =  (p_1 ^ x_1) + (p_2 ^ x_2) + . . . + (p_m ^ x_m)
        // where p_1,...,p_n are the unique prime divisors of n 
        //    and x_1,...,x_n are the number of times each divisor appears in the prime factoring of n 
        // then the number of divisors for n = (x_1 + 1) * (x_2 + 1) * ... * (x_m * p_m)
        //@formatter:on

        // we could brute force it
        // for each number calculate the prime factoring then calculate the number of divisors

        System.out.println("Start Time: " + new DateTime());

        boolean found = false;
        int i = 1;
        long triangle = 0;
        while (!found) {
            triangle += i++;
            int numDivisors = numDivisors(triangle);
            if (numDivisors > 500) {
                found = true;
            }
        }

        System.out.println("First triangle number with 500 divisors: " + triangle);
        System.out.println("It is the " + i + "th triangle number;");
        System.out.println("Stop Time: " + new DateTime());
        // Answer: 76576500 in ~260 ms
    }

    public static int numDivisors(long value) {
        List<Long> primeFactors = Utilities.primeFactorize(value);

        // can iterate over the list one time to calculate this
        long lastValue = primeFactors.get(0);
        int valueCount = 1;
        int numDivisors = 1;
        for (int j = 1; j < primeFactors.size(); j++) {
            if (primeFactors.get(j) == lastValue) {
                // same number as the last one, just increment the number of times we've seen
                // this value
                valueCount++;
            } else {
                // new value
                lastValue = primeFactors.get(j);
                // increase the divisor count based on the previous value
                numDivisors *= (valueCount + 1);
                valueCount = 1;
            }
        }

        // increase divisor count one last time
        numDivisors *= (valueCount + 1);

        return numDivisors;
    }
}
